def lmis(X):
    n=len(X)
    M=[None]*(n+1) #M[0] stores L, current max length subsequence
    P=[None]*n
    M[0]=0
    for i in range(n):
        j=bst(X,M,X[i])
        if j!=0:
            P[i]=M[j]
        if j==M[0] or X[i]<X[M[j+1]]:
            M[j+1]=i
            if M[0]==0 or j==M[0]:
                M[0]+=1
    return M,P
def bst(X,M,x):
    L=M[0]
    low=1
    high=L
    mid=(low+high)//2
    while low<=high:
        mid=(low+high)//2
        if x>=X[M[mid]]:
            if mid==L:
                return L
            elif x<X[M[mid+1]]:
                return mid
            else:
                low=mid+1
        else: #x<X[M[mid]]
            if mid==1:
                return 0
            else:
                high=mid-1
    return mid
def print_lmis(X,P,i):
    if P[i] is None:
        print X[i],
    else:
        print_lmis(X,P,P[i])
        print X[i],
def do_print_lmis(X,P):
    print_lmis(X,P,M[M[0]])

if __name__=='__main__':
    X=[0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
    #X=[8,4,12,2,6,10]
    M,P=lmis(X)
    print 'M:', M
    print 'P:', P
    print 'lmis:',
    do_print_lmis(X,P)
